/*
 * disk_reader.c
 *
 *  Created on: Feb 19, 2012
 *      Author: albert
 */
#define _GNU_SOURCE

#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <stdio.h>
#include "disk_reader.h"
#include "util.h"

void disk_init() {

	page_size = getpagesize();
	page_limit = page_size / SECTOR_SIZE;

	if ((disk_file = open("./disk1.img", O_DIRECT)) < 0) {
		perror("FATAO: Failed to open disk image. \n");
		printf("%s\n", strerror(errno));
		exit(-1);
	}
}

/* Reads several sectors within a page (typically 4096 bytes)
 * returns the number of sectors read, or -1 if an error has occurred.
 *
 */
int read_in_page(int* sectors, unsigned long int** bufs, int length) {
	int i= 0, j = 0;
	int min = MAX_SECTOR, max = 0;
	int start = 0;

	for (i = 0; i < length; i++) {
		if (sectors[i] < min)
			min = sectors[i];
		if (sectors[i] > max)
			max = sectors[i];
	}

	if (min < 0 || max > MAX_SECTOR) {
		fprintf(stderr, "invalid reading arguments. min = %d, max = %d .\n",
				min, max);
		return -1;
	}

	if (max - min > page_size / SECTOR_SIZE) {
		fprintf(stderr,
				"Max and min are not in the same page. min = %d, max = %d .\n",
				min, max);
		return -1;
	}

	if (disk_buffer == 0) {
		int rtn = 0;
		if (rtn = posix_memalign(&disk_buffer, page_size, page_size)) {
			perror("Memalign failed");
			if (rtn == EINVAL)
				fprintf(stderr, "EINVAL");
			if (rtn == ENOMEM)
				fprintf(stderr, "ENOMEM");
			return -1;
		}
	}

	// seek to the start of the diskfile

	start = min * SECTOR_SIZE;
	//fprintf(stderr, "min = %d, max = %d. seeking: %d.\n", min, max, start);
	lseek(disk_file, start, SEEK_SET);

	if (read(disk_file, disk_buffer, page_size) == -1) {
		fprintf(stderr, "Error reading disk: %s\n", strerror(errno));
		return -1;
	}

	//fprintf(stderr, "copying...");
	for (i = 0; i < length; i++) {
		int offset = SECTOR_SIZE / sizeof(unsigned long int) * (sectors[i] - min); ///
		unsigned long int* cur_buffer = bufs[i];

		//fprintf(stderr, "offset = %d \n", offset);
		//fprintf(stderr, "cur_buf = %u \n", cur_buffer);
		//SECTOR_SIZE / sizeof(unsigned long int)
		for (j = 0; j < SECTOR_SIZE / sizeof(unsigned long int); j++) {
			cur_buffer[j] = disk_buffer[offset + j];
		}

		//fprintf(stderr, "disk location %d -> %x \n", offset * 4 + start, disk_buffer[offset + 0]);
		//fprintf(stderr, "disk location %d -> %x \n", offset * 4 + start + 1, disk_buffer[offset + 1]);
	}
	//fprintf(stderr, "copied %d\n", disk_buffer);

	//free(disk_buffer);

	//fprintf(stderr, "freed\n");
	return length;
}

int cscan_read(int* sectors, unsigned long int** bufs, int length) {
	if (quick_sort(sectors, bufs, length))
		fprintf(stderr, "quick sort failed.\n");

	int page_sectors[8];
	unsigned int* page_bufs[8];
	int cache_retrieved[length];
	int i = 0, j = 0, num_retrieved = 0;

	// retrieve anything from cache if possible
	for (i = 0; i < length; i++) {
		if (cache_contains(sectors[i])) {
			copy_cache_to(sectors[i], bufs[i]);
			cache_retrieved[num_retrieved++] = i;
		}
	}

	//fprintf(stderr, "cached contains: ");
	print_array(cache_retrieved, num_retrieved);

	// remove retrieved requests from the request queue
	int remaining_sectors[length - num_retrieved];
	unsigned long int* remaining_bufs[length - num_retrieved];

	i = 0;
	j = 0;

	for (i = 0; i < length; i++) {
		if (!array_contains(cache_retrieved, sectors[i], num_retrieved)) {
			remaining_sectors[j] = sectors[i];
			remaining_bufs[j] = bufs[i];
			j++;
		}
	}

	//fprintf(stderr, "inside ");
	//for (i = 0; i < 10; i++) {
	//	fprintf(stderr, "%d -> %d \n", sectors[i], bufs[i]);
	//}

	print_array(remaining_sectors, length);
	//fprintf(stderr, "inside \n");
	print_array(remaining_bufs, length);
	// process remaining requests

	i = 0;
	j = 0;
	int first_sector;
	int start_position;
	while (i < length) {
		// split requests into pages
		// 1) find the last sector number we can access within one page
		first_sector = remaining_sectors[i];
		start_position = i;
		i++;
		//fprintf(stderr, "next round %d\n", i);
		while ((remaining_sectors[i] - first_sector) < page_limit && i < length)
			i++;

		for (j = 0; j < i - start_position; j++) {
			page_sectors[j] = remaining_sectors[start_position + j];
			page_bufs[j] = remaining_bufs[start_position + j];
		}
		//fprintf(stderr, "grouped: ");
		print_array(page_sectors, i - start_position);
		read_in_page(page_sectors, page_bufs, i - start_position);
	}

	return length;
}

int quick_sort(int* arr, unsigned long int** bufs, int length) {

#define  MAX_LEVELS  1000

	int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;
	unsigned long int* piv_ptr;

	beg[0] = 0;
	end[0] = length;
	while (i >= 0) {
		L = beg[i];
		R = end[i] - 1;
		if (L < R) {
			piv = arr[L];
			piv_ptr = bufs[L];
			if (i == MAX_LEVELS - 1)
				return -1;
			while (L < R) {
				while (arr[R] >= piv && L < R)
					R--;
				if (L < R) {
					arr[L] = arr[R];
					bufs[L++] = bufs[R];
				}
				while (arr[L] <= piv && L < R)
					L++;
				if (L < R) {
					arr[R] = arr[L];
					bufs[R--] = bufs[L];
				}
			}
			arr[L] = piv;
			bufs[L] = piv_ptr;
			beg[i + 1] = L + 1;
			end[i + 1] = end[i];
			end[i++] = L;
		} else {
			i--;
		}
	}
	return 0;
}

//  quickSort
//
//  This public-domain C implementation by Darel Rex Finley.
//
//  * Returns YES if sort was successful, or NO if the nested
//    pivots went too deep, in which case your array will have
//    been re-ordered, but probably not sorted correctly.
//
//  * This function assumes it is called with valid parameters.
//
//  * Example calls:
//    quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4
//    quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7

int quickSort(int *arr, int elements) {

#define  MAX_LEVELS  1000

	int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;

	beg[0] = 0;
	end[0] = elements;
	while (i >= 0) {
		L = beg[i];
		R = end[i] - 1;
		if (L < R) {
			piv = arr[L];
			if (i == MAX_LEVELS - 1)
				return -1;
			while (L < R) {
				while (arr[R] >= piv && L < R)
					R--;
				if (L < R)
					arr[L++] = arr[R];
				while (arr[L] <= piv && L < R)
					L++;
				if (L < R)
					arr[R--] = arr[L];
			}
			arr[L] = piv;
			beg[i + 1] = L + 1;
			end[i + 1] = end[i];
			end[i++] = L;
		} else {
			i--;
		}
	}
	return 0;
}
